package com.demo.example.hot100;

public class FindTheFirstAndLastInSortedArray {
    public static void main(String[] args) {
        for(int i:searchRange(new int[]{5,7,7,8,8,10},8)){
            System.out.println(i);
        }
    }
    public static int[] searchRange(int[] nums,int target){
        if(nums==null || nums.length==0){
            return new int[]{-1,-1};
        }
        //要求log 那么必然是要使用二分查找了
        int left=0,right=nums.length-1;
        int first=0; //target第一次出现的位置
        int end=0; //target最后一次出现的位置
        while(left<=right){
            int mid=left+((right-left)>>1);
            if(nums[mid]==target){
                //分别向前向后找最开始和最后的位置
                first=mid;
                end=mid;
                while(end+1< nums.length && nums[end]==target && target==nums[end+1]){
                    end++;
                }
                while(first-1>=0 && nums[first]==target && target==nums[first-1]){
                    first--;
                }
                return new int[]{first,end};
            }
            if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return new int[] {-1,-1};
    }
}
